package J.算法.贪婪算法;

import java.util.*;

/**
 * GREEDY：每次都选最优解
 */
public class _尚硅谷_电台覆盖问题 {

    /**
     * 初始数据：HashMap(String,HashSet<String>) 存放电台数据
     * key为电台种类，value为每种电台所覆盖的城市列表
     */
    public void test(HashMap<String, HashSet<String>> map){
        //1-未遍历城市集合 将所有城市不重复的push进去(常规要遍历map )
        HashSet<String > rest = new HashSet<>();
        rest.add("bj");
        rest.add("xA");

        //2-创建 创建ArrayList 存放被选择的电台
        List<String> select = new ArrayList<>();
        // 3-记录盖被放入的电台key索引
        String maxKey = null;
        //当前对应的未覆盖
        List<String> noCover = new ArrayList<>();
        while (rest.size()!= 0){

            //遍历电台
            for (String key:map.keySet()){

                //当前key对应的城市
                HashSet<String> area = map.get(key);

                noCover.addAll(area);
                noCover.retainAll(rest);//取交集


                //更新maxSize 当前未覆盖的量 大于 ，max指针指向的那个未覆盖量
                if (noCover.size() >0 && (maxKey == null || noCover.size() > map.get(maxKey).size())){

                    maxKey = key;
                }
                //循环下一个 就要把交集集合清空
                noCover.clear();
            }

            //循环结束 进行更新
            maxKey = null;

            if (maxKey != null){

                select.add(maxKey);
                //从rest删除本次遍历城市
                rest.removeAll(map.get(maxKey));
            }

        }






    }

}
